//最小覆盖子串
public class leetcode76 {
    public String minWindow(String ss, String tt) {
        int begin=-1;
        int minlen=Integer.MAX_VALUE;
        int[] hash1=new int[128];
        int[] hash2=new int[128];
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        int len=0;
        for(char x:t){
            if(hash1[x]==0){
                len++;
            }
            hash1[x]++;
        }


        int left=0;
        int count=0;//统计有效字符出现的总类
        for(int right=0;right<s.length;right++){
            char in=s[right];
            hash2[in]++;
            if(hash2[in]==hash1[in]){
                count++;
            }
            while(count==len){
                if(right-left+1<minlen){
                    begin=left;
                    minlen=right-left+1;
                }
                char out=s[left];
                if(hash2[out]==hash1[out]){
                    count--;
                }
                hash2[out]--;
                left++;

            }
        }
        if(begin==-1){
            return new String();
        } else{
            return ss.substring(begin,begin+minlen);
        }
    }
}
